public class Percolation {

	private int side = -1;
	private int top;

	private int[] states = null;
	private WeightedQuickUnionUF cellStorage;

	private Object lock = new Object();

	public Percolation(int N) {
		if (N <= 0) {
			throw new IllegalArgumentException(
					"IllegalArgument. N is smaller or equal to 0.");
		}
		side = N;
		states = new int[N * N + 1];
		cellStorage = new WeightedQuickUnionUF(N * N + 1);
		for (int ii = 1; ii <= N * N; ii++) {
			states[ii] = 0;
		}
		top = 0;
		states[top] = 1;
	}

	public boolean percolates() {
		synchronized (lock) {
			int j = 1;
			while (j <= side) {
				if (isFull(side, j)) {
					return true;
				} else {
					j++;
				}
			}
			return false;
		}
	}

	public void open(int i, int j) {
		synchronized (lock) {
			if (isIndexOutOfBounds(i, j)) {
				throw new IndexOutOfBoundsException(
						"Index is out of the boundaries.");
			}
			if (isOpen(i, j)) {
				return;
			}
			int cell = getCellIndex(i, j);
			states[cell] = 1;
			// we first check to see if the cell is located at the top
			if (i > 1 && i != side && isOpen(i - 1, j)) {
				connectCells(getCellIndex(i - 1, j), cell);
			} else if (i == 1) {

				connectCells(top, cell);
			}
			// we check to see if the cell is at the bottom
			if (i <= side - 1 && isOpen(i + 1, j)) {
				connectCells(getCellIndex(i + 1, j), cell);
			} else if (i == side && isOpen(i - 1, j)) {
				connectCells(getCellIndex(i - 1, j), cell);
			}

			if ((j > 1 || j == side) && isOpen(i, j - 1)) {
				connectCells(getCellIndex(i, j - 1), cell);
			} else if ((j == 1 || j < side) && isOpen(i, j + 1)) {
				connectCells(getCellIndex(i, j + 1), cell);
			}
		}
	}

	private int getCellIndex(int i, int j) {
		if (side < 0) {
			return -1;
		}
		return (i - 1) * side + j;
	}

	private void connectCells(int cell1, int cell2) {

		cellStorage.union(cell1, cell2);
	}

	public boolean isOpen(int i, int j) {
		synchronized (lock) {
			if (isIndexOutOfBounds(i, j))
				throw new IndexOutOfBoundsException(
						"Index is out of the boundaries.");
			else if (states[getCellIndex(i, j)] == 1) {
				return true;
			}
			return false;
		}
	}

	public boolean isFull(int m, int n) {
		synchronized (lock) {
			if (isIndexOutOfBounds(m, n)) {
				throw new IndexOutOfBoundsException(
						"Index is out of the boundaries.");
			} else {
				return cellStorage.connected(getCellIndex(m, n), top);
			}
		}
	}

	private boolean isIndexOutOfBounds(int i, int j) {
		if (states == null || states.length == 0) {
			return true;
		}
		if (i <= 0 || i > side) {
			return true;
		}
		if (j <= 0 || j > side) {
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		int N = 4;
		Percolation perc = new Percolation(N);
		perc.open(4, 1);
		perc.open(3, 1);
		perc.open(2, 1);
		perc.open(1, 1);
		perc.open(1, 4);
		perc.open(2, 4);
		perc.open(4, 4);
		// perc.open(2, 1);
		// perc.open(1, 1);
		boolean isFull = perc.isFull(4, 4);
		StdOut.println("is full : " + isFull);
		// it doesn't percolate now
		StdOut.println("The system percolates:" + perc.percolates());
		// new test
		// Percolation perc2 = new Percolation(10);
		// perc2.isOpen(0, 6);

	}
}
